package com.zlk.algorithm.dataStructure.tree.treeDp;

import com.zlk.algorithm.dataStructure.tree.NodeUtils;
import com.zlk.algorithm.dataStructure.tree.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @program: algorithm
 * @ClassName lowestAncestor
 * @description:给定一棵二叉树的头节点head，和另外两个节点a和b，返回a和b的最低公共祖先
 * @author: slfang
 * @create: 2024-02-21 14:23
 * @Version 1.0
 **/
public class LowestAncestor {


    //可能性：
    //     经过x  a在树 b在树  一个在子树   一个在树外
    //     不经x  都在左树 都在右树  都在树外
    //信息： hasA  hasB
    //

    class Info{
        boolean hasA;
        boolean hasB;

        TreeNode lowestAncestor;


        public Info(boolean hasA, boolean hasB,TreeNode lowestAncestor) {
            this.hasA = hasA;
            this.hasB = hasB;
            this.lowestAncestor = lowestAncestor;
        }
    }


    public  TreeNode lowestAncestor2(TreeNode head, TreeNode a, TreeNode b) {
        return process(head, a, b).lowestAncestor;
    }
    public Info process(TreeNode x,TreeNode a,TreeNode b){
        if(x==null){
            return new Info(false, false, null);
        }
        Info leftInfo = process(x.left, a, b);
        Info rightInfo = process(x.right, a, b);
        boolean findA = (x == a) || leftInfo.hasA || rightInfo.hasA;
        boolean findB = (x == b) || leftInfo.hasB || rightInfo.hasB;
        TreeNode ans = null;
        if (leftInfo.lowestAncestor != null) {
            ans = leftInfo.lowestAncestor;
        } else if (rightInfo.lowestAncestor != null) {
            ans = rightInfo.lowestAncestor;
        } else {
            //应为上面leftInfo.lowestAncestor != null)    rightInfo.lowestAncestor != null
            if (findA && findB) {
                ans = x;
            }
        }
        return new Info(findA, findB, ans);

    }

    public  TreeNode lowestAncestor1(TreeNode head, TreeNode o1, TreeNode o2) {
        if (head == null) {
            return null;
        }
        // key的父节点是value
        HashMap<TreeNode, TreeNode> parentMap = new HashMap<>();
        parentMap.put(head, null);
        fillParentMap(head, parentMap);
        HashSet<TreeNode> o1Set = new HashSet<>();
        TreeNode cur = o1;
        o1Set.add(cur);
        while (parentMap.get(cur) != null) {
            cur = parentMap.get(cur);
            o1Set.add(cur);
        }
        cur = o2;
        while (!o1Set.contains(cur)) {
            cur = parentMap.get(cur);
        }
        return cur;
    }

    public static void fillParentMap(TreeNode head, HashMap<TreeNode, TreeNode> parentMap) {
        if (head.left != null) {
            parentMap.put(head.left, head);
            fillParentMap(head.left, parentMap);
        }
        if (head.right != null) {
            parentMap.put(head.right, head);
            fillParentMap(head.right, parentMap);
        }
    }


    public  TreeNode pickRandomOne(TreeNode head) {
        if (head == null) {
            return null;
        }
        ArrayList<TreeNode> arr = new ArrayList<>();
        fillPrelist(head, arr);
        int randomIndex = (int) (Math.random() * arr.size());
        return arr.get(randomIndex);
    }

    public  void fillPrelist(TreeNode head, ArrayList<TreeNode> arr) {
        if (head == null) {
            return;
        }
        arr.add(head);
        fillPrelist(head.left, arr);
        fillPrelist(head.right, arr);
    }
    @Test
    public void test(){
        int maxLevel = 4;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            TreeNode head = NodeUtils.generateRandomBST(maxLevel, maxValue);
            TreeNode o1 = pickRandomOne(head);
            TreeNode o2 = pickRandomOne(head);
            if (lowestAncestor1(head, o1, o2) != lowestAncestor2(head, o1, o2)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }





}
